#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // ysh's method
    int maxSubArray(vector<int> &nums)
    {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int max_sum = nums[0];
        for (size_t i = 1; i < nums.size(); i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            if (dp[i] > max_sum)
            {
                max_sum = dp[i];
            }
        }
        return max_sum;
    }

    // book's method greedy_algorithm
    // int maxSubArray(vector<int> &nums)
    // {
    //     int result = INT_MIN;
    //     int count = 0;
    //     for (size_t i = 0; i < nums.size(); i++)
    //     {
    //         count += nums[i];
    //         if (count > result)
    //         {
    //             result = count;
    //         }
    //         if (count < 0)
    //         {
    //             count = 0;
    //         }
    //     }
    //     return result;
    // }
};

int main()
{
    vector<int> nums{-2, 1, -3, 4, -1, 2, 1, -5, 4};
    Solution sol;
    cout << sol.maxSubArray(nums) << endl;
    return 0;
}